package 剑指offer_专项突击版.简单;

/**
 * 给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。
 * <p>
 *  
 * <p>
 * 示例 1:
 * <p>
 * 输入: n = 2
 * 输出: [0,1,1]
 * 解释:
 * <p>
 * 奇数：二进制中，奇数1的个数比前面偶数1的个数多1个，因为低位会多个1  dp[i] = dp[i-1] + 1
 * 偶数：偶数1的个数和除以2之后的数1的个数相同，因为低位都是0，所以去除一个0对1的个数没有影响 dp[i] = dp[i>>1];
 * <p>
 * <p>
 * 0 0
 * 1 1      1
 * 2 10     1
 * 3 11     2
 * <p>
 * 4 100    1
 * 5 101    2
 * 6 110    2
 * 7 111    3
 * <p>
 * 8 1000   1
 * 9 1001   2
 * 10 1010  2
 * 11 1011  3
 * 12 1100  2
 * 13 1101  3
 * 14 1110  3
 * 15 1111  4
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/w3tCBm
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author caihe
 * @date 2022/10/27 11:29
 */
public class _003_前n个数字二进制中1的个数 {
    /**
     * 奇数：二进制中，奇数1的个数比前面偶数1的个数多1个，因为低位会多个1  dp[i] = dp[i-1] + 1
     * 偶数：偶数1的个数和除以2之后的数1的个数相同，因为低位都是0，所以去除一个0对1的个数没有影响 dp[i] = dp[i>>1];
     * dp[i] = dp[i>>1] + (i & 1);
     */
    public int[] countBits(int n) {
        int[] res = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            res[i] = res[i >> 1] + (i & 1);
        }
        return res;
    }
}
